﻿#pragma once

#include <iostream>
#include <vector>

using std::cout;
using std::endl;

#ifdef _WIN32
	#include <windows.h>
#else
	// ...linunx系统调用头文件
#endif

// 定长内存池
//template<size_t N>
//class ObjectPool
//{ };

// 直接去堆上按⻚申请空间 
inline static void* SystemAlloc(size_t kpage) //一页8k
{
#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE,PAGE_READWRITE);
#else
		// linux下brk mmap等 
#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
	return ptr;
}


// 用对象大小实现定长内存池
template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		if (_freelist)
		{
			void* next = *(void**)_freelist;
			obj = (T*)_freelist;
			_freelist = next;
		}
		else
		{
			if (_remainBytes < sizeof(T)) // 当剩余空间大小小于一个对象大小时才申请空间
			{
				_remainBytes = 128 * 1024;
				//_memory = (char*)malloc(_remainBytes); // 128k
				_memory = (char*)SystemAlloc(_remainBytes >> 13); // 128k÷8 => 几页
				if (_memory == nullptr)
					throw std::bad_alloc();
			}

			obj = (T*)_memory;
			// 至少开一个指针大小
			size_t size = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += size;
			_remainBytes -= size;
		}

		// 显示调用构造，定位new
		new(obj)T;

		return obj;
	}

	void Delete(T* obj)
	{
		// 显示调析构
		obj->~T();

		// 头插
		*(void**)obj = _freelist;
		_freelist = obj;
	}

private:
	char* _memory = nullptr; // 指向申请的大块内存
	size_t _remainBytes = 0; // 内存池剩余空间大小

	void* _freelist = nullptr; // 释放内存时维护的释放内存块，指向已释放内存节点
};


struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{
	}
};

void TestObjectPool()
{
	// 申请释放的轮次 
	const size_t Rounds = 3;
	// 每轮申请释放多少次 
	const size_t N = 100000;

	std::vector<TreeNode*> v1;
	v1.reserve(N);

	size_t begin1 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v1.push_back(new TreeNode);
		}
		for (int i = 0; i < N; ++i)
		{
			delete v1[i];
		}
		v1.clear();
	}
	size_t end1 = clock();


	ObjectPool<TreeNode> TNPool;
	std::vector<TreeNode*> v2;
	v2.reserve(N);

	size_t begin2 = clock();
	for (size_t j = 0; j < Rounds; ++j)
	{
		for (int i = 0; i < N; ++i)
		{
			v2.push_back(TNPool.New());
		}
		for (int i = 0; i < N; ++i)
		{
			TNPool.Delete(v2[i]);
		}
		v2.clear();
	}
	size_t end2 = clock();

	cout << "new cost time:" << end1 - begin1 << endl;
	cout << "object pool cost time:" << end2 - begin2 << endl;
}